Peripheral devices may utilize an expansion bus to couple to and communicate with a computer system. Examples of expansion busses include the Industry Standard Architecture (ISA), Enhanced ISA (EISA), Micro Channel Architecture (MCA), Video Electronics Standards Association Local Bus (VESA or VL), Personal Computer Memory Card Industry Association (PCMCIA), Small Computer System Interface (SCSI), Peripheral Component Interconnect (PCI), IEEE 1394 (Firewire), and the Universal Serial Bus (USB). In a USB system, one or more USB peripheral devices are coupled via a shared USB interconnect to a single host computer system including client and USB system software as well as a USB host controller hardware interface. The USB supports functional data and control exchange between the USB host and a USB device as a set of one or more logical channels or “pipes” between client software and a particular endpoint on a USB device. Each pipe is associated with one of four USB-defined transfer types which are optimized for different client and device service requirements.
Because the USB provides a shared physical transfer medium, bandwidth must be allocated among client software transfer requests. When a transfer request for a particular pipe is received from a client application, USB system software puts the request into the appropriate format and adds it to a schedule data structure or “transaction list” depending on the pipe's associated transfer type. An asynchronous schedule data structure is utilized for control and bulk transfer types while isochronous and interrupt transfers are placed into a periodic schedule data structure to ensure proper transmission latency. Once enabled, the schedules are executed by the host controller of the USB hardware interface to generate transactions on the USB. As the schedules are traversed, the host controller may cache the context or “state” of the schedule including schedule data structure elements or “work items”.
The removal and reclamation of work items from the periodic and asynchronous schedules is similarly handled by USB system software. When a work item is removed from a schedule data structure however, it is unknown whether the host controller has a copy of the removed work item or a reference to it stored in cache. The removed work item cannot be reclaimed (i.e. its associated memory cannot be freed or reused) until it is determined that all cached state or data structures relating to the removed work item have been evicted or “released” by the host controller. Since the periodic schedule must regularly advance to ensure transmission latency for isochronous transfers, cache flushes occur on a periodic (frame or micro-frame) basis after which a removed periodic schedule work item may be reclaimed. Accordingly, in USB systems including a single schedule data structure, the coherency of the schedule may be ensured by waiting a predetermined amount of time after a work item is removed to reclaim it. In some USB systems however, separate periodic and asynchronous schedule data structures are defined. Consequently, methods for reclaiming asynchronous schedule work items in such systems based on the passage of time have proven inadequate to accurately determine when a removed asynchronous schedule data structure work item may be reclaimed to ensure asynchronous schedule coherency.